package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 09:52
 **/

import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：没有重复元素的重排列
 * 题目详述 ：
 * 给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
 */
public class Permute {
    /**
     * 思路 ：回溯法
     * 全排列 ：
     * （1）与组合不同之处，在于排列中元素前后顺序不一样的话，那么其就算是一种排列;
     * （2）全排列，与一般的排列区别在于，是对于数组nums中的所有元素进行全排列;
     * ===> 不存在判断是否该元素是否选择加入，因为该nums数组中的所有元素都会被加入到全排列中;
     * 其选择，应该是后续应该选取哪个元素;（前index - 1个元素是选择好的;）
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        flushBack(nums , 0 , result);
        return result;
    }

    private void flushBack(int[] nums, int index, List<List<Integer>> result) {
        if(index == nums.length){
            List<Integer> num = new LinkedList<>();
            // 由于我们是通过对于nums数组中元素进行位置交换操作，来实现获取当前数组所有可能的全排列
            // 即，当index == nums.length时，我们需要将当时nums中元素顺序地存储到num集合;
            for (int i : nums) {
                num.add(i);
            }
            result.add(num);
        }
        // 即，前index - 1个元素是已经选择好的;
        /**
         * 思考 ：为什么i = index，即i是从index下标开始遍历？
         * 原因 ：当前所已经被选择好的（即，固定的）为nums数组中前index - 1个元素，而同时nums数组中第index个元素还未选择;
         *       所以还是需要对于第index个元素进行选择;
         */
        // 添加限制条件（index < nums.length）;
        // 即，若是index >= nums.length时，就会直接返回;
        else if(index < nums.length){
            for(int i = index ; i < nums.length ; i++){
                swap(nums , index , i);
                flushBack(nums , index + 1 , result);
                // 恢复到修改之前的状态;
                // 为什么呢？ 因为我们是通过对于nums数组中元素进行交换位置，同时将修改后的nums数组结果存储到result集合中;
                swap(nums , index , i);
            }
        }

    }
    // 传入nums数组，将nums数组中index和i下标所对应的数组元素进行交换
    private void swap(int[] nums , int index, int i) {
        if(index != i){
            int temp = nums[index];
            nums[index] = nums[i];
            nums[i] = temp;
        }
    }

    /**
     * 分析 ：
     * （1）时间复杂度 ：O（n!）
     * （2）空间复杂度 ：由于递归调用栈的深度为n，即空间复杂度O（n）;
     */
}
